package com.kehao.leetcode.order;

import org.junit.Test;

public class LeetcodeSolution1049 {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int i = 0; i < stones.length; i++) {
            sum+=stones[i];
        }
        int target = sum/2;
        boolean[][] dp = new boolean[stones.length+1][target+1];
        dp[0][0] = true;

        for (int i = 1; i < stones.length + 1; i++) {
            for (int j = 0; j < target + 1; j++) {
                if(j>=stones[i-1]){
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-stones[i-1]];
                }else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }

        for (int i = target; i >=0; i--) {
            if(dp[stones.length][i]){
                return sum-2*i;
            }
        }
        return 0;
    }


}
